/**
* This file is part of programmer.
* Description: 
* If you use this code, please cite the respective publications as
* listed on the above website.
*
* programmer is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* programmer is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with programmer. If not, see <http://www.gnu.org/licenses/>.
*
* @file        alarm.cpp
* @brief       Defines the 
* @author      Ziqiang Wang
* @email       1531651@tongji.edu.cn
* @date        2021/12/10
* @copyright   Copyright (c) 2021
*----------------------------------------------------------------------------*
*  Remark         : Description                                              *
*----------------------------------------------------------------------------*
*  Change History :                                                          *
*  <Date>     | <Version> | <Author>       | <Description>                   *
*----------------------------------------------------------------------------*
*  2021/12/10    | 1.0.0.0   | Ziqiang Wang   | Create file                     *
*----------------------------------------------------------------------------*
*                                                                            *
*/

#include "alarm.h"

/*实现一个闹钟系统AlarmSystem，简单来说就是实现三个方法：
addAlarm：
添加闹钟，包括属性id、weekdays[]、hour、minute，typeId。其中weekdays表示在星期几响起，可能的取值为1-7。typeId表示闹钟的类型，可能的取值为0，1，2。如果之前已经添加过相同id的闹钟，则不再添加，返回false，否则返回true
        deleteAlarm：
根据id删除闹钟，如果不存在此id的闹钟，则返回false，否则删除后返回 true
queryAlarm：
给定weekday、hour、startminute、endminute，查询在weekday这一天，hour这一小时，startminute到endminute之间会响起的闹钟，如果有多个则优先按照响起的时间先后排序输出，如果响起时间一样，则按照闹钟的类型从小到大排序，如果闹钟类型也一样，则按照id从小到大排序。*//*

class AlarmSystem {
public:
    AlarmSystem()
    {

    }

    bool AddAlarm(int id, int hour, int minute, const vector<int>& weekdays, int typeId)
    {
        auto it = alarmCache.find(id);
        if (it != alarmCache.end()) {
            return false;
        }
        Alarm alarm(id, hour * 100 + minute, typeId, weekdays); // 100
        alarmCache.insert({id, alarm});
        for (const auto & day : weekdays) {
            dayAlarmId[day].push_back(id);
        }
        return true;
    }

    bool DeleteAlarm(int id)
    {
        auto it = alarmCache.find(id);
        if (it == alarmCache.end()) {
            return false;
        }
        for (const auto & delteDay : alarmCache[id].weekdays) {
            vector<int> newId;
            for (const auto & canId : dayAlarmId[delteDay]) {
                if (canId != id) {
                    newId.push_back(canId);
                }
            }
            dayAlarmId[delteDay] = newId;
        }
        alarmCache.erase(id);
        return true;
    }

    vector<int> QueryAlarm(int weekday, int hour, int startMinute, int endMinute)
    {
        vector<int> result;
        auto it = dayAlarmId.find(weekday);
        if (it == dayAlarmId.end()) {
            return result;
        }
        int start = hour * 100 + startMinute; // 100
        int end = hour * 100 + endMinute; // 100
        auto& thisDayAlarm = dayAlarmId[weekday];
        vector<int> candidate;
        for (const auto & alarmId : thisDayAlarm) {
            auto alarm = alarmCache[alarmId];
            if ((alarm.time >= start) && (alarm.time <= end)) {
                candidate.push_back(alarmId);
            }
        }
        set<Alarm> alarmSet;
        for (const auto & alarmId : candidate) {
            alarmSet.insert(alarmCache[alarmId]);
        }
        for (const auto & alarm : alarmSet) {
            result.push_back(alarm.id);
        }
        return result;
    }

    struct Alarm {
        int id;
        int time;
        int type;
        vector<int> weekdays;
        Alarm() = default;
        Alarm(int idPara, int timePara, int typePara, const vector<int>& weekdaysPara) : id(idPara), time(timePara), type(typePara), weekdays(weekdaysPara) {}
        bool operator < (const Alarm &another) const
        {
            if (time != another.time) {
                return time < another.time;
            } else if (type != another.type) {
                return type < another.type;
            }
            return id < another.id;
        }
    };
    map<int, Alarm> alarmCache;
    map<int, vector<int>> dayAlarmId;

};
*/

/*现有一个二叉树 root ，每个节点都有一个值，它的深度为从根到该节点的唯一路径长（根的深度为 1）。

给定一个整型列表 target，target[i]对应的「最大深度」定义为：

· 若二叉树中存在节点值大于 target[i] 的节点，则这些节点中最大的深度为 target[i] 的「最大深度」；

· 若二叉树中不存在节点值大于 target[i] 的节点，则 target[i] 的「最大深度」为 -1。

请计算 target 中每个元素的「最大深度」，并按 target 下标顺序依次存入序列返回。
示例 1：

输入：
target = [2,7]
root = [5,3,7,1,5]

输出：[3,-1]

解释：
首先确定每个节点的深度，
target[0] = 2：节点值大于 2 的节点有root[0]、root[1]、root[2]、root[4]，其中root[4]深度最大（为 3），所以其「最大深度」为 3；
target[1] = 7：没有大于 7 的节点，所以其「最大深度」为 -1；
最后返回 [3,-1]。

示例 2：

输入：
target = [6,2,9,7,9]
root = [3,4,11,3,null,null,8,7,null,5]

输出：[4,4,2,3,2]

解释：

target[0] = 6：节点值大于 6 的节点有root[2]、root[6]、root[7]，其中root[7]深度最大（为 4），所以其「最大深度」为 4；
target[1] = 2：所有非空节点的值都大于2，所以其「最大深度」为 4；
target[2] = 9：大于 9 的节点只有root[2]，所以其「最大深度」为 2；
target[3] = 7：大于 7 的节点有root[2]、root[6]，所以其「最大深度」为 3；
target[4] = 9：大于 9 的节点只有root[2]，所以其「最大深度」为 2；
最后返回 [4,4,2,3,2]。

提示：

· 1 <= target.length <= 10^5
· 1 <= target[i] <= 10^5
· 1 <= 节点总数 <= 50000 且 1 <= 节点值 <= 10^5

此题对效率有要求，请考虑高效的实现方式*//*

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    void DFS(const TreeNode* root, int depth)
    {
        if (root == nullptr) {
            return;
        }
        auto it = valMaxDepth.find(root->val);
        if (it == valMaxDepth.end()) {
            valMaxDepth[root->val] = depth;
        } else {
            valMaxDepth[root->val] = max(depth, valMaxDepth[root->val]);
        }
        if (root->left) {
            DFS(root->left, depth + 1);
        }
        if (root->right) {
            DFS(root->right, depth + 1);
        }
    }

    vector<int> ValueDepth(const vector<int>& target, const TreeNode* root)
    {
        DFS(root, 1);
        int lastMax = -1;
        map<int, int> valToEndMaxDepth;
        for (auto it = valMaxDepth.rbegin(); it != valMaxDepth.rend(); ++it) {
            auto maxDepth = max(lastMax, it->second);
            valToEndMaxDepth[it->first] = maxDepth;
            lastMax = maxDepth;
        }

        vector<int> result;
        for (int i = 0; i < target.size(); ++i) {
            auto tarNum = target[i];
            int maxDep = -1;
            for (auto it = valToEndMaxDepth.upper_bound(tarNum); it != valToEndMaxDepth.end() ; it++) {
                maxDep = max(maxDep, it->second);
            }
            if (maxDep == -1) {
                result.push_back(-1);
            } else {
                result.push_back(maxDep);
            }
        }
        return result;
    }
    map<int, int> valMaxDepth;
};*/

/*
给定一棵二叉树，从树根到树叶定义为一条路径，树的每个节点都有值（可能存在重复）。对于一条路径，如果该节点前后节点值的和恰好相等，则将节点标记，如路径7-3-3-1-1-8，这条路径上7+3 =
1+1+8，所以第三个节点被标记。求最后所有未被标记的节点的和。
*//*

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <utility>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:

    void DFS(TreeNode* root, int lastSum, vector<TreeNode*> &path, vector<int> &sum,
             vector<vector<TreeNode*>> &allPath)
    {
        if (root->left == nullptr && root->right == nullptr) {
            path.push_back(root);
            lastSum += root->val;
            allPath.push_back(path);
            path.pop_back();
            sum.push_back(lastSum);
            lastSum -= root->val;
            return;
        }

        if (root->left) {
            path.push_back(root);
            lastSum += root->val;
            DFS(root->left, lastSum, path, sum, allPath);
            path.pop_back();
            lastSum -= root->val;
        }

        if (root->right) {
            path.push_back(root);
            lastSum += root->val;
            DFS(root->right, lastSum, path, sum, allPath);
            path.pop_back();
            lastSum -= root->val;
        }
    }

    void Travel(TreeNode* root, const set<TreeNode*> &markNode, int &res)
    {
        if (root == nullptr) {
            return;
        } else if (markNode.find(root) == markNode.end()) {
            res += root->val;
        }
        Travel(root->left, markNode, res);
        Travel(root->right, markNode, res);
    }


    int BisectTreePath(const TreeNode* root)
    {
        int lastSum = 0;
        vector<TreeNode*> path;
        vector<int> sum;
        vector<vector<TreeNode*>> allPath;
        DFS(const_cast<TreeNode *>(root), lastSum, path, sum, allPath);

        set<TreeNode*> markNode;
        for (int i = 0; i < allPath.size(); ++i) {
            int currentSum = 0;
            for (int j = 0; j < allPath[i].size(); ++j) {
                if ((currentSum * 2 + allPath[i][j]->val) == sum[i]) { // 2
                    markNode.insert(allPath[i][j]);
                }
                currentSum += allPath[i][j]->val;
            }
        }

        int res = 0;
        Travel(const_cast<TreeNode *>(root), markNode, res);

        return res;
    }
};*/

/*请你设计一个租房系统。支持以下几个函数：

boolean addRoom(int id, int area, int price, int rooms, int[] address)：向系统中加入房号为 id 的房子。id:
房间编号，area：房间面积，price：房间租金，rooms：房间对应数量，address：房间平面坐标(x坐标，y坐标；长度为2)。

执行 addRoom 操作：

1）若租房系统中已经存在房号为id的房间，则更新该房间的信息为新加入的信息，同时返回false；

2）若租房系统中已经不存在房号为id的房间，则更新该房间的信息为新加入的信息，同时返回true。

boolean deleteRoom(int id)：从系统中移除房号为id的房子。

1)若租房系统中已经存在房号为id的房间，则将该房间从系统移除，返回true；

2)若租房系统中不存在房号为id的房间，返回false。

int[] queryRoom(int area, int price, int rooms, int[] address, int[][] orderBy)：查询满足指定规则的房间。

查询规则：

找出当前租房系统中房间面积大于等于area，租金小于等于price，房间数量等于rooms的房间，将这些房间按照orderBy指定的规则进行升序或者降序排列，orderBy的每一个元素为( parameter,order)，其中parameter可能取值为1（按照面积排序） 2 (按照租金排序) 3(曼哈顿距离排序)，order可能的取值1 （升序排列） -1（降序排列）
，曼哈顿距离由查询的address和满足面积大于等于area，租金小于等于price，房间数量等于rooms的房间对应address求解 |x1-x2|+|y1-y2|*//*

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <utility>
#include <algorithm>
using namespace std;

class RentingSystem {
public:

    struct Room {
        int id = 0;
        int area = 0;
        int price = 0;
        int rooms = 0;
        int manhatonDis = 0;
        vector<int> address;
        vector<vector<int>> orderBy;

        Room() = default;
        Room(int id_, int area_, int price_, int rooms_, const vector<int> &address_) :
        id(id_), area(area_), price(price_), rooms(rooms_), address(address_) {}

        bool operator <(const Room &another) const {
            if (!orderBy.empty()) {
                for (int i = 0; i < orderBy.size(); i++) {
                    bool res = false;
                    if (orderBy[i][0] == 1 && area != another.area) {
                        res = (area < another.area);
                    } else if (orderBy[i][0] == 2 && price != another.price) {
                        res = (price < another.price);
                    } else if (orderBy[i][0] == 3 && manhatonDis != another.manhatonDis) {
                        res = (manhatonDis < another.manhatonDis);
                    } else {
                        continue;
                    }
                    return orderBy[i][1] == 1 ? res : !res;
                }
            }
            return id < another.id;
        }

    };

    map<int, Room> allRooms;


    RentingSystem()
    {

    }

    bool AddRoom(int id, int area, int price, int rooms, const vector<int>& address)
    {
        Room room(id, area, price, rooms, address);
        allRooms[id] = room;

        if (allRooms.find(id) == allRooms.end()) {
            return true;
        } else {
            return false;
        }
    }

    bool DeleteRoom(int id)
    {
        if (allRooms.find(id) != allRooms.end()) {
            allRooms.erase(id);
        } else {
            return false;
        }
        return true;
    }

    vector<int> QueryRoom(int area, int price, int rooms, const vector<int>& address, const vector<vector<int>>& orderBy)
    {
        vector<int> res;
        set<Room> candidateRoom;
        for (const auto &idRoom : allRooms) {
            auto room = idRoom.second;
            if (room.rooms == rooms && room.area >= area && room.price <= price) {
                room.orderBy = orderBy;
                room.manhatonDis = abs(room.address[0] - address[0])
                                 + abs(room.address[1] - address[1]);
                candidateRoom.insert(room);
            }
        }

        for (const auto &room: candidateRoom) {
            res.push_back(room.id);
        }
        return res;
    }



};*/

/*

 在某OS的文件系统中（同一目录下的目录和文件不会重名），假设当前目录为根目录，给定若干个已有路径（目录或文

件），其格式如下：

·         输入均为根目录下的路径，且不会重复给出；

·         路径中目录或文件名仅包含字母、数字和分隔符/；

·         路径结尾带/表示目录，否则是文件。例如 var/log/是目录，etc/profile是文件。

请按照以下规则，将输入的路径整理成树状结构并输出：

·         同一父目录下的目录或文件按字典序升序输出，大小写敏感

·         第一层目录或文件无需缩进；后续每深入一层，需要多缩进两个空格

·         输出时目录和文件都不含/

解答要求时间限制：1000ms, 内存限制：256MB

输入

第一行一个整数 num，表示路径的数量，取值范围 [1,1000]

接下来 num 行，每行一个路径字符串，长度范围 [1,255]

用例保证输入的路径合法，且不会以/开头

输出

按行输出树状结构的路径

 样例

输入样例 1

5

usr/local/lib64

GAMES

usr/DRIVERS

home

var/log/

输出样例

GAMES

home

usr

  DRIVERS

  local

    lib64

var

  log

 *//*


class Solution {
public:

    struct Node {
        string file;
        Node(string file_) : file(file_) {}
        map<string, shared_ptr<Node>> children;
        bool operator < (const Node &another) const
        {
            return file < another.file;
        }
    };
    shared_ptr<Node> root;

    void makeTree(vector<string>& fileName)
    {
        root = make_shared<Node>("");
        auto r = root;
        for (const auto &file : fileName) {
            string path;
            for (int i = 0; i < file.size(); ++i) {
                if (file[i] == '/' || i == file.size() - 1) {
                    if (file[i] != '/' && i == file.size() - 1) {
                        path.push_back(file[i]);
                    }

                    auto it = r->children.find(path);
                    if (it == r->children.end()) {
                        auto node = make_shared<Node>(path);
                        r->children.insert({path, node});
                    }
                    r = r->children[path];
                    path.clear();
                } else {
                    path.push_back(file[i]);
                }
            }
            r = root;
        }
    }

    void printTree(shared_ptr<Node>& r, vector<string>& result, int level)
    {
        for (auto& x : r->children) {
            string w;
            for (int i = 0; i < level; ++i) {
                w.push_back(' ');
                w.push_back(' ');
            }
            w.append(x.first);
            result.push_back(w);
            printTree(x.second, result, 1 + level);
        }
    }
    vector<string> path(vector<string>& fileName)
    {
        makeTree(fileName);
        vector<string> result;
        printTree(root, result, 0);
        return result;
    }


};
*/